COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00012 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\def\fnc#1{\mathop{\rm #1}\nolimits}
\rm
\line{\sevenrm a05.tex[106,phy] \today\hfill}

\bigskip\noindent
{\bf Tournament Sorting} (for section on data structures).

Some of our example algorithms have shown that searching a table is much faster
if that table is sorted.  How much would you pay for a dictionary or a phone
book if they were not alphabetized?  Here is an algorithm for sorting that is
simple, yet efficient.  For $n$ data, make a tree like the one below, with
$2n-1$ circles:

$$\vcenter{\halign{\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad
&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad
&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\cr
&&&&&&&1\cr
\noalign{\smallskip}
&&&2&&&&&&&&3\cr
\noalign{\medskip}
&4&&&&5&&&&6&&&&7\cr
\noalign{\bigskip}
8&&9&&10&&11&&12&&13&&\phantom{12}\cr}}$$

\bigskip\noindent
In the example, $n=7$.  Put your data in the last $n$ circles, 
which have no other circles hanging from them,

$$\vcenter{\halign{\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad
&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad
&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\cr
&&&&&&&1\cr
\noalign{\smallskip}
&&&2&&&&&&&&3\cr
\noalign{\medskip}
&4&&&&5&&&&6&&&&7\cr
&&&&&&&&&&&&&Sun\cr
\noalign{\medskip}
8&&9&&10&&11&&12&&13&&\phantom{12}\cr
Mon&&Tue&&Wed&&Thu&&Fri&&Sat&&\phantom{Sun}\cr}}$$

\vfill\eject

\noindent
Treat the diagram like the pairings for a tournment.  Player 12, Fri, plays
Player~13, Sat.  The winner is Fri, because her name is alphabetically earlier;
Fri's name and number go in circle number~6, and we continue counting down
until we have a winner in circle~1:

$$\vcenter{\halign{\ctr{#}$\;$&\ctr{#}$\;$&\ctr{#}$\;$&\ctr{#}$\;$
&\ctr{#}$\;$
&\ctr{#}$\;$&\ctr{#}$\;$&\ctr{#}$\;$&\ctr{#}$\;$&\ctr{#}$\;$&\ctr{#}$\;$
&\ctr{#}$\;$&\ctr{#}$\;$&\ctr{#}$\;$&\ctr{#}$\;$&\ctr{#}$\;$&\ctr{#}$\;$
&\ctr{#}$\;$&\ctr{#}$\;$&\ctr{#}$\;$&\ctr{#}$\;$&\ctr{#}$\;$&\ctr{#}$\;$
&\ctr{#}$\;$&\ctr{#}$\;$&\ctr{#}$\;$&\ctr{#}$\;$&\ctr{#}\cr
&&&&&&&&&&&&&&1&12\cr
&&&&&&&&&&&&&&&Fri\cr
\noalign{\smallskip}
&&&&&&2&8&&&&&&&&&&&&&&&3&12\cr
&&&&&&&Mon&&&&&&&&&&&&&&&&Fri\cr
\noalign{\medskip}
&&4&8&&&&&&&5&11&&&&&&&6&12&&&&&&&7&7\cr
&&&Mon&&&&&&&&Thu&&&&&&&&Fri&&&&&&&&Sun\cr
\noalign{\medskip}
8&8&&&9&9&&&10&10&&&11&11&&&12&12&&&13&13\cr
&Mon&&&&Tue&&&&Wed&&&&Thu&&&&Fri&&&&Sat&&&&\phantom{1}\cr}}$$

\bigskip\noindent
The winner is Fri, player 12.  We write or record the winner, then disqualify Fri
to see who comes in second.  To disqualify Fri, we change circle~12 
to ZZZ and
work upward in the diagram, through circles 6, 3, and~1, finding new winners:


$$\vcenter{\halign{\ctr{#}$\,$&\ctr{#}$\,$&\ctr{#}$\,$&\ctr{#}$\,$
&\ctr{#}$\,$
&\ctr{#}$\,$&\ctr{#}$\,$&\ctr{#}$\,$&\ctr{#}$\,$&\ctr{#}$\,$&\ctr{#}$\,$
&\ctr{#}$\,$&\ctr{#}$\,$&\ctr{#}$\,$&\ctr{#}$\,$&\ctr{#}$\,$&\ctr{#}$\,$
&\ctr{#}$\,$&\ctr{#}$\,$&\ctr{#}$\,$&\ctr{#}$\,$&\ctr{#}$\,$&\ctr{#}$\,$
&\ctr{#}$\,$&\ctr{#}$\,$&\ctr{#}$\,$&\ctr{#}$\,$&\ctr{#}\cr
&&&&&&&&&&&&&&1&8\cr
&&&&&&&&&&&&&&&Mon\cr
\noalign{\smallskip}
&&&&&&2&8&&&&&&&&&&&&&&&3&13\cr
&&&&&&&Mon&&&&&&&&&&&&&&&&Sat\cr
\noalign{\medskip}
&&4&8&&&&&&&5&11&&&&&&&6&13&&&&&&&7&7\cr
&&&Mon&&&&&&&&Thu&&&&&&&&Sat&&&&&&&&Sun\cr
\noalign{\medskip}
8&8&&&9&9&&&10&10&&&11&11&&&12&12&&&13&13\cr
&Mon&&&&Tue&&&&Wed&&&&Thu&&&&ZZZ&&&&Sat&&&&\phantom{0}\cr}}$$

\bigskip\noindent
We keep recording and disqualifying winners until we have counted $n$ winners
(or until the winner is ZZZ).

To program this algorithm, we must be able to follow the connections up and down.
The circles are numbered from 1 to $2n-1$.  If a circle has number $i<n$, 
the two below it are numbered $2i$ and $2i+1$.  If $i>1$, 
the one above it is numbered $i\hbox{ DIV }2$. In Pascal, the algorithm follows:

\vfill\eject

\bigskip
\halign{\qq\lft{\tt #}\cr
\qq	PROGRAM TOURNAMENT (\qq		);\cr
\qq	declarations\cr
\qq	BEGIN\cr
\qq	FOR I:= 1 TO 2*N-1 DO NUMBR[I]:=I;\cr
\qq	FOR I:= N TO 2*N-1 DO READ(PLAYER[I]);\cr
\qq	FOR I:= N-1 DOWN TO 1 DO\cr
\qq\qq		IF PLAYER [2*I+1]<PLAYER[2*I] THEN\cr
\qq\qq\qq		BEGIN\cr
\qq\qq\qq		NUMBER[I]:=NUMBER[2*I]\cr
\qq\qq\qq		PLAYER[I]:=PLAYER[2*I]\cr
\qq\qq\qq		END\cr
\qq\qq		ELSE\cr
\qq\qq\qq		BEGIN\cr
\qq\qq\qq		NUMBER[I]:=NUMBER[2*I+1]\cr
\qq\qq\qq		PLAYER[I]:=PLAYER[2*I+1]\cr
\qq\qq\qq		END;\cr
\qq	WHILE PLAYER[1]<`ZZZ' DO\cr
\qq\qq		BEGIN\cr
\qq\qq		WRITE(PLAYER[1]);\cr
\qq\qq 		J:=NUMBR[1];\cr
\qq\qq		PLAYER[J]:=`ZZZ';\cr
\qq\qq		WHILE J>1 DO\cr
\qq\qq\qq		BEGIN\cr
\qq\qq\qq		I:=J DIV 2;\cr
\qq\qq		IF PLAYER[2*I]<PLAYER[2*I] THEN\cr
\qq\qq\qq		BEGIN\cr
\qq\qq\qq		NUMBER[I]:=NUMBER[2*I]\cr
\qq\qq\qq		PLAYER[I]:=PLAYER[2*I]\cr
\qq\qq\qq		END\cr
\qq\qq		ELSE\cr
\qq\qq\qq		BEGIN\cr
\qq\qq\qq		NUMBER[I]:=NUMBER[2*I+1]\cr
\qq\qq\qq		PLAYER[I]:=PLAYER[2*I+1]\cr
\qq\qq\qq		END;\cr
\qq\qq		END;\cr
\qq\qq		J:=I\cr
\qq\qq		END(*WHILE J*)\cr
\qq	END(*WHILE PLAYER*)\cr
END(*PROGRAM*)\cr}

\vfill\eject

This algorithm, applied to 1000 data, finds the first with 999 comparisons on the
input data.  Thereafter, every other item on the sorted list is produced with at
most ten comparisons, for a total of about 11000.  Most comparably simple sorting
algorithms would require 500000 comparisons.

The arrays used by the tournament sorting algorithm have an implicit structure of
connections among the array elements, allowing us to get from an array element to
the elements above or below it in the tree.  Such a structure of connections
among data is called, unsurprisingly, a `data structure'.  The most common data
structure of an array is one 
in which element~$i$ is connected to element $i+1$. There
are many other structures, simple and complicated, on which useful algorithms
have been based.

\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft May 16, 1984

\bye